package priv.conceit.study.leetcode.simple.official;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * 编号101
 * 验证是否为对称二叉树
 * <a href="hhttps://leetcode-cn.com/problems/symmetric-tree/solution/dui-cheng-er-cha-shu-by-leetcode/"></a>
 * 给定一个二叉树，检查它是否是镜像对称的。
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 * 1
 * / \
 * 2   2
 * / \ / \
 * 3  4 4  3
 * <p>
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 * 1
 * / \
 * 2   2
 * \   \
 * 3    3
 * <p>
 * 解题思路：
 * 1-递归
 * left和right都为null 返回true
 * 只有一方为null 返回false
 * 每次递归都判断形参作用值是否相等
 * 且
 * root.left和root.right
 * 和
 * root.right和root.left都作为形参
 * 递归
 * 时间复杂度o(n)
 * 因为每个节点都会得到执行，n就是节点总数
 * 空间复杂度o(n)
 * 递归调用的次数受树的高度限制。在最糟糕情况下，树是线性的，其高度为 O(n)。由栈上的递归调用造成的空间复杂度为 O(n)
 *
 * 2-队列广度优先遍历
 * 队列每次入队四个节点
 * left.left=right.right
 * left.right=right.left
 * 出队是前两个节点 对应的是left.left和right.right，left.right和right.left
 * 只要前两个节点都不为空或者值不相同则false
 * 时间复杂度o(n)
 * 因为每个节点都会得到执行，n就是节点总数
 * 空间复杂度o(n)
 * 搜索队列需要额外的空间。在最糟糕情况下，队列中插入 O(n) 个结点。因此，空间复杂度为 O(n)。
 *
 *
 * @author Conceit
 * @since 1.0.0, 2019/7/18
 */
public class SymmetricTree {

	public static void main(String[] args) {

	}

	public boolean isSymmetric(TreeNode root) {
		if(Objects.isNull(root)){
			return Boolean.TRUE;
		}
		boolean allIsNull=Objects.isNull(root.left)&&Objects.isNull(root.right);
		boolean difference=Objects.isNull(root.left)||Objects.isNull(root.right);
		if(allIsNull){
			return Boolean.TRUE;
		}
		if(difference){
			return Boolean.FALSE;
		}

		//return SymmetricTree.bfs(root.left,root.right);
		return this.recursion(root.left,root.right);

	}

	/**
	 * 递归调用
	 *
	 * @return
	 */
	public  boolean recursion(TreeNode left,TreeNode right){

		boolean allIsNull=Objects.isNull(left)&&Objects.isNull(right);
		boolean difference=Objects.isNull(left)||Objects.isNull(right);
		if(allIsNull){
			return Boolean.TRUE;
		}
		if(difference){
			return Boolean.FALSE;
		}
		if(left.val!=right.val){
			return Boolean.FALSE;
		}

		return recursion(left.left,right.right)&&recursion(left.right,right.left);
	}

	/**
	 * 迭代调用
	 * 广度优先
	 *
	 * @return
	 */
	public  boolean bfs(TreeNode left,TreeNode right){
		Queue<TreeNode> treeNodeQueue=new LinkedList<>();
		treeNodeQueue.add(left);
		treeNodeQueue.add(right);
		while (!treeNodeQueue.isEmpty()){
			//出队
			TreeNode curLeft=treeNodeQueue.poll();
			TreeNode curRight=treeNodeQueue.poll();

			//逻辑判断
			//1-数值判断
			//2-都为空继续处理
			//3-有一方为空则打回
			boolean allIsNull=Objects.isNull(curLeft)&&Objects.isNull(curRight);
			boolean difference=Objects.isNull(curLeft)||Objects.isNull(curRight);
			if(allIsNull){
				continue;
			}
			if(difference){
				return Boolean.FALSE;
			}
			if(curLeft.val!=curRight.val){
				return Boolean.FALSE;
			}

			//入队
			treeNodeQueue.add(curLeft.left);
			treeNodeQueue.add(curRight.right);
			treeNodeQueue.add(curLeft.right);
			treeNodeQueue.add(curRight.left);
		}
		return Boolean.TRUE;

	}

	public class TreeNode {
		int val;
		TreeNode left;

		TreeNode right;
		TreeNode(int x) {
			val = x;
		}

	}
}
